External Memory Pipelining Made Easy With TPIE

摘要

When handling large datasets that exceed the capacity of the main memory,movement of data between main memory and external memory (disk), rather thanactual (CPU) computation time, is often the bottleneck in the computation.Since data is moved between disk and main memory in large contiguous blocks,this has led to the development of a large number of I/O-efficient algorithmsthat minimize the number of such block movements. TPIE is one of two major libraries that have been developed to supportI/O-efficient algorithm implementations. TPIE provides an interface where liststream processing and sorting can be implemented in a simple and modular waywithout having to worry about memory management or block movement. However, ifcare is not taken, such streaming-based implementations can lead to practicallyinefficient algorithms since lists of data items are typically written to (andread from) disk between components. In this paper we present a major extension of the TPIE library that includesa pipelining framework that allows for practically efficient streaming-basedimplementations while minimizing I/O-overhead between streaming components. Theframework pipelines streaming components to avoid I/Os between components, thatis, it processes several components simultaneously while passing output fromone component directly to the input of the next component in main memory. TPIEautomatically determines which components to pipeline and performs the requiredmain memory management, and the extension also includes support forparallelization of internal memory computation and progress tracking across anentire application. The extended library has already been used to evaluateI/O-efficient algorithms in the research literature and is heavily used inI/O-efficient commercial terrain processing applications by the Danish startupSCALGO.